class Solution
{
public:
    void push(int node) {
        stackIn.push(node);
    }

    int pop() {
        int ret = 0;
        if(!stackOut.empty())
        {
            ret =  stackOut.top();
            stackOut.pop();
        }
        else if(stackOut.empty() && !stackIn.empty())
        {
            while(!stackIn.empty())
            {
                int val = stackIn.top();
                stackIn.pop();

                stackOut.push(val);
            }

            ret = stackOut.top();
            stackOut.pop();
        }

        return ret;
    }

private:
    stack<int> stackIn;
    stack<int> stackOut;
};

class Solution {
public:
    void push(int value) {
        st.push(value);
        if(stMin.empty())
        {
            stMin.push(value);
        }
        else if(!stMin.empty() && value <= stMin.top())
        {
            stMin.push(value);
        }
        else if(!stMin.empty() && value > stMin.top())
        {
            stMin.push(stMin.top());
        }
    }

    void pop() {
        st.pop();
        stMin.pop();
    }

    int top() {
        return st.top();
    }

    int min() {
        return stMin.top();
    }

private:
    stack<int> st;
    stack<int> stMin;
};

class Solution {
public:
    bool isValid(string s) {
        bool ret = false;
        stack<char> st;
        int i = 0;

        if(s.size() == 0 || s.size() % 2 == 1)
        {
            ret = false;
        }
        else 
        {
            for(i = 0; i < s.size(); ++i)
            {
                if(s[i] == '(' || s[i] == '[' || s[i] == '{')
                {
                    st.push(s[i]);
                }
                else if(s[i] == ')' && !st.empty() && st.top() == '(') 
                {
                    st.pop();
                }
                else if(s[i] == ']' && !st.empty() && st.top() == '[')
                {
                    st.pop();
                }
                else if(s[i] == '}' && !st.empty() && st.top() == '{')
                {
                    st.pop();
                }
            }    
        }

        if(st.empty() && i == s.size())
            ret = true;

        return ret;
    }
};
